package com.lun.easy;


import java.util.LinkedList;

import com.lun.util.NAryTree.Node;

public class MaximumDepthOfNAryTree {
	
	//方法一：DFS + Java8
    public int maxDepth(Node root) {
        int max = 0;
    	if(root == null) return max;
    	
        if(root.children != null)
        	max = root.children.stream().map(a->maxDepth(a))//
        		.max((a1, a2)->a1-a2).orElse(0);
    	
    	return max + 1;
    }
	
    
    //方法二：BFS
    public int maxDepth2(Node root) {
    	if(root == null) return 0;
    	LinkedList<Node> queue = new LinkedList<>();
    	queue.offer(root);
    	int depth = 0;
    	while(!queue.isEmpty()) {
    		depth++;
    		for(int size = queue.size(); size > 0; size--) {
    			Node node = queue.poll();
    			if(node.children != null)
    				queue.addAll(node.children);
    		}
    	}
    	return depth;
    }
    
    //方法三：DFS
    public int maxDepth3(Node root) {
    	if(root == null) return 0;
    	
    	int max = 0;
        if(root.children != null) {
        	for(Node node : root.children) {
        		int temp = maxDepth3(node);
        		max = Math.max(max, temp);
        	}
        }
    	return max + 1;
    }
    
}
